package 力扣._1462_课程表4;

import java.util.*;

public class Solution {


    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        Map<Integer, Set<Integer>> arcmap = new HashMap<>();    //k,k的所有先行课程
        for (int[] prerequisite : prerequisites) {
            Set<Integer> set = arcmap.getOrDefault(prerequisite[1], new HashSet<>());
            set.add(prerequisite[0]);
            arcmap.put(prerequisite[1], set);

            Set<Integer> keySet = arcmap.keySet();
            for (Integer key : keySet) {
                Set<Integer> set1 = arcmap.get(key);
                if (set1.contains(prerequisite[1]))
                    set1.add(prerequisite[0]);
            }
            Set<Integer> set1 = arcmap.get(prerequisite[0]);
            if(set1!=null)
                for (Integer integer : set1) {
                    set.add(integer);
                }
            arcmap.put(prerequisite[1], set);
        }

        List<Boolean> result = new LinkedList<>();
        for (int[] query : queries) {
            int now = query[1];
            int goal = query[0];
            Set<Integer> set = arcmap.get(now);
            if (set != null)
                result.add(set.contains(goal));
            else
                result.add(false);
        }
        return result;
    }

    public static void main(String[] args) {
        int numCourses = 5;
        int[][] prerequisites = new int[][]{{0,1},{1,2},{2,3},{3,4}};
        int[][] queries = {{0,4},{4,0},{1,3},{3,0}};
        List<Boolean> booleans = new Solution().checkIfPrerequisite(numCourses, prerequisites, queries);
        System.out.println(booleans.toString());
    }
}
